home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Python 1.4 / Python 1.4 source / Extensions / img / genmap.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-03-18  |  9.8 KB  |  371 lines  |  [TEXT/CWIE]
  1. /*
  2. ** genmap - Generate a colormap with the specified number of
  3. ** entries.
  4. **
  5. ** Jack Jansen, CWI, 1995.
  6. **
  7. ** Modified from ppmquant.c, which is
  8. **
  9. ** Copyright (C) 1989, 1991 by Jef Poskanzer.
  10. **
  11. ** Permission to use, copy, modify, and distribute this software and its
  12. ** documentation for any purpose and without fee is hereby granted, provided
  13. ** that the above copyright notice appear in all copies and that both that
  14. ** copyright notice and this permission notice appear in supporting
  15. ** documentation.  This software is provided "as is" without express or
  16. ** implied warranty.
  17. */
  18.  
  19. #include "Python.h"
  20. #include "mppmcmap.h"
  21.  
  22. #define MAXCOLORS 32767
  23.  
  24. /* #define LARGE_NORM */
  25. #define LARGE_LUM
  26.  
  27. /* #define REP_CENTER_BOX */
  28. /* #define REP_AVERAGE_COLORS */
  29. #define REP_AVERAGE_PIXELS
  30.  
  31. typedef struct box* box_vector;
  32. struct box
  33.     {
  34.     int ind;
  35.     int colors;
  36.     int sum;
  37.     };
  38.  
  39. typedef int (*qsfuncptr)Py_PROTO((const void *, const void *));
  40.  
  41. static int mediancut Py_PROTO((colorhist_vector chv, int colors, int sum,
  42.                    int newcolors, pixel *colormap));
  43. static int redcompare Py_PROTO((colorhist_vector ch1, colorhist_vector ch2));
  44. static int greencompare Py_PROTO((colorhist_vector ch1, colorhist_vector ch2));
  45. static int bluecompare Py_PROTO((colorhist_vector ch1, colorhist_vector ch2));
  46. static int sumcompare Py_PROTO((box_vector b1, box_vector b2));
  47.  
  48. int
  49. mppm_genmap(pixels, cols, rows, mapdata, newcolors)
  50.     long *pixels;
  51.     int cols, rows;
  52.     long *mapdata;
  53.     int newcolors;
  54. {
  55. #if 0
  56.     int argc;
  57.     char* argv[];
  58.     {
  59.     FILE* ifp;
  60.     pixel** pixels;
  61.     pixel** mappixels;
  62.     register pixel* pP;
  63.     int argn, rows, cols, maprows, mapcols, row;
  64.     register int col, limitcol;
  65.     pixval maxval, newmaxval, mapmaxval;
  66.     int newcolors, colors;
  67.     register int ind;
  68.     colorhash_table cht;
  69.     int floyd;
  70.     int usehash;
  71.     long* thisrerr;
  72.     long* nextrerr;
  73.     long* thisgerr;
  74.     long* nextgerr;
  75.     long* thisberr;
  76.     long* nextberr;
  77.     long* temperr;
  78.     register long sr, sg, sb, err;
  79. #define FS_SCALE 1024
  80.     int fs_direction;
  81.     char* usage = "[-floyd|-fs] <ncolors> [ppmfile]\n                 [-floyd|-fs] -map mapfile [ppmfile]";
  82. #endif
  83.     colorhist_vector chv;
  84.     int colors, rv;
  85.  
  86.     /*
  87.     ** Step 2: attempt to make a histogram of the colors, unclustered.
  88.     */
  89.     chv = mppm_computecolorhist(pixels, cols, rows, MAXCOLORS, &colors );
  90.     if ( chv == (colorhist_vector) 0 ) {
  91.     return 0;
  92. #if 0
  93.     XXXX this code should go to a separate 'scale' routine.
  94.         pm_message( "too many colors!" );
  95.     newmaxval = maxval / 2;
  96.     pm_message(
  97.      "scaling colors from maxval=%d to maxval=%d to improve clustering...",
  98.            maxval, newmaxval );
  99.     for ( row = 0; row < rows; ++row )
  100.         for ( col = 0, pP = pixels[row]; col < cols; ++col, ++pP )
  101.         MPPM_DEPTH( *pP, *pP, maxval, newmaxval );
  102.     maxval = newmaxval;
  103. #endif
  104.     }
  105.     /*
  106.     ** Step 3: apply median-cut to histogram, making the new colormap.
  107.     */
  108.     rv = mediancut( chv, colors, rows * cols, newcolors, mapdata );
  109.     mppm_freecolorhist( chv );
  110.     return rv;
  111. }
  112.  
  113. /*
  114. ** Here is the fun part, the median-cut colormap generator.  This is based
  115. ** on Paul Heckbert's paper "Color Image Quantization for Frame Buffer
  116. ** Display", SIGGRAPH '82 Proceedings, page 297.
  117. */
  118.  
  119. #if __STDC__
  120. static int
  121. mediancut( colorhist_vector chv, int colors, int sum,
  122.       int newcolors, pixel *colormap )
  123. #else /*__STDC__*/
  124. static int
  125. mediancut( chv, colors, sum, newcolors, colormap )
  126.     colorhist_vector chv;
  127.     int colors, sum, newcolors;
  128.     pixel *colormap;
  129. #endif /*__STDC__*/
  130.     {
  131.     box_vector bv;
  132.     register int bi, i;
  133.     int boxes;
  134.  
  135.     bv = (box_vector) malloc( sizeof(struct box) * newcolors );
  136.     if ( bv == (box_vector) 0 ) {
  137.     return -1;
  138.     }
  139.  
  140.     /*
  141.     ** Set up the initial box.
  142.     */
  143.     bv[0].ind = 0;
  144.     bv[0].colors = colors;
  145.     bv[0].sum = sum;
  146.     boxes = 1;
  147.  
  148.     /*
  149.     ** Main loop: split boxes until we have enough.
  150.     */
  151.     while ( boxes < newcolors )
  152.     {
  153.     register int indx, clrs;
  154.     int sm;
  155.     register int minr, maxr, ming, maxg, minb, maxb, v;
  156.     int halfsum, lowersum;
  157.  
  158.     /*
  159.     ** Find the first splittable box.
  160.     */
  161.     for ( bi = 0; bi < boxes; ++bi )
  162.         if ( bv[bi].colors >= 2 )
  163.         break;
  164.     if ( bi == boxes )
  165.         break;    /* ran out of colors! */
  166.     indx = bv[bi].ind;
  167.     clrs = bv[bi].colors;
  168.     sm = bv[bi].sum;
  169.  
  170.     /*
  171.     ** Go through the box finding the minimum and maximum of each
  172.     ** component - the boundaries of the box.
  173.     */
  174.     minr = maxr = MPPM_GETR( chv[indx].color );
  175.     ming = maxg = MPPM_GETG( chv[indx].color );
  176.     minb = maxb = MPPM_GETB( chv[indx].color );
  177.     for ( i = 1; i < clrs; ++i )
  178.         {
  179.         v = MPPM_GETR( chv[indx + i].color );
  180.         if ( v < minr ) minr = v;
  181.         if ( v > maxr ) maxr = v;
  182.         v = MPPM_GETG( chv[indx + i].color );
  183.         if ( v < ming ) ming = v;
  184.         if ( v > maxg ) maxg = v;
  185.         v = MPPM_GETB( chv[indx + i].color );
  186.         if ( v < minb ) minb = v;
  187.         if ( v > maxb ) maxb = v;
  188.         }
  189.  
  190.     /*
  191.     ** Find the largest dimension, and sort by that component.  I have
  192.     ** included two methods for determining the "largest" dimension;
  193.     ** first by simply comparing the range in RGB space, and second
  194.     ** by transforming into luminosities before the comparison.  You
  195.     ** can switch which method is used by switching the commenting on
  196.     ** the LARGE_ defines at the beginning of this source file.
  197.     */
  198. #ifdef LARGE_NORM
  199.     if ( maxr - minr >= maxg - ming && maxr - minr >= maxb - minb )
  200.         qsort(
  201.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  202.         (qsfuncptr)redcompare );
  203.     else if ( maxg - ming >= maxb - minb )
  204.         qsort(
  205.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  206.         (qsfuncptr)greencompare );
  207.     else
  208.         qsort(
  209.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  210.         (qsfuncptr)bluecompare );
  211. #endif /*LARGE_NORM*/
  212. #ifdef LARGE_LUM
  213.     {
  214.     pixel p;
  215.     float rl, gl, bl;
  216.  
  217.     MPPM_ASSIGN(p, maxr - minr, 0, 0);
  218.     rl = MPPM_LUMIN(p);
  219.     MPPM_ASSIGN(p, 0, maxg - ming, 0);
  220.     gl = MPPM_LUMIN(p);
  221.     MPPM_ASSIGN(p, 0, 0, maxb - minb);
  222.     bl = MPPM_LUMIN(p);
  223.  
  224.     if ( rl >= gl && rl >= bl )
  225.         qsort(
  226.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  227.         (qsfuncptr)redcompare );
  228.     else if ( gl >= bl )
  229.         qsort(
  230.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  231.         (qsfuncptr)greencompare );
  232.     else
  233.         qsort(
  234.         (char*) &(chv[indx]), clrs, sizeof(struct colorhist_item),
  235.         (qsfuncptr)bluecompare );
  236.     }
  237. #endif /*LARGE_LUM*/
  238.     
  239.     /*
  240.     ** Now find the median based on the counts, so that about half the
  241.     ** pixels (not colors, pixels) are in each subdivision.
  242.     */
  243.     lowersum = chv[indx].value;
  244.     halfsum = sm / 2;
  245.     for ( i = 1; i < clrs - 1; ++i )
  246.         {
  247.         if ( lowersum >= halfsum )
  248.         break;
  249.         lowersum += chv[indx + i].value;
  250.         }
  251.  
  252.     /*
  253.     ** Split the box, and sort to bring the biggest boxes to the top.
  254.     */
  255.     bv[bi].colors = i;
  256.     bv[bi].sum = lowersum;
  257.     bv[boxes].ind = indx + i;
  258.     bv[boxes].colors = clrs - i;
  259.     bv[boxes].sum = sm - lowersum;
  260.     ++boxes;
  261.     qsort( (char*) bv, boxes, sizeof(struct box), (qsfuncptr)sumcompare );
  262.     }
  263.  
  264.     /*
  265.     ** Ok, we've got enough boxes.  Now choose a representative color for
  266.     ** each box.  There are a number of possible ways to make this choice.
  267.     ** One would be to choose the center of the box; this ignores any structure
  268.     ** within the boxes.  Another method would be to average all the colors in
  269.     ** the box - this is the method specified in Heckbert's paper.  A third
  270.     ** method is to average all the pixels in the box.  You can switch which
  271.     ** method is used by switching the commenting on the REP_ defines at
  272.     ** the beginning of this source file.
  273.     */
  274.     for ( bi = 0; bi < boxes; ++bi )
  275.     {
  276. #ifdef REP_CENTER_BOX
  277.     register int indx = bv[bi].ind;
  278.     register int clrs = bv[bi].colors;
  279.     register int minr, maxr, ming, maxg, minb, maxb, v;
  280.  
  281.     minr = maxr = MPPM_GETR( chv[indx].color );
  282.     ming = maxg = MPPM_GETG( chv[indx].color );
  283.     minb = maxb = MPPM_GETB( chv[indx].color );
  284.     for ( i = 1; i < clrs; ++i )
  285.         {
  286.         v = MPPM_GETR( chv[indx + i].color );
  287.         minr = min( minr, v );
  288.         maxr = max( maxr, v );
  289.         v = MPPM_GETG( chv[indx + i].color );
  290.         ming = min( ming, v );
  291.         maxg = max( maxg, v );
  292.         v = MPPM_GETB( chv[indx + i].color );
  293.         minb = min( minb, v );
  294.         maxb = max( maxb, v );
  295.         }
  296.     MPPM_ASSIGN(
  297.         colormap[bi], ( minr + maxr ) / 2, ( ming + maxg ) / 2,
  298.         ( minb + maxb ) / 2 );
  299. #endif /*REP_CENTER_BOX*/
  300. #ifdef REP_AVERAGE_COLORS
  301.     register int indx = bv[bi].ind;
  302.     register int clrs = bv[bi].colors;
  303.     register long r = 0, g = 0, b = 0;
  304.  
  305.     for ( i = 0; i < clrs; ++i )
  306.         {
  307.         r += MPPM_GETR( chv[indx + i].color );
  308.         g += MPPM_GETG( chv[indx + i].color );
  309.         b += MPPM_GETB( chv[indx + i].color );
  310.         }
  311.     r = r / clrs;
  312.     g = g / clrs;
  313.     b = b / clrs;
  314.     MPPM_ASSIGN( colormap[bi], r, g, b );
  315. #endif /*REP_AVERAGE_COLORS*/
  316. #ifdef REP_AVERAGE_PIXELS
  317.     register int indx = bv[bi].ind;
  318.     register int clrs = bv[bi].colors;
  319.     register long r = 0, g = 0, b = 0, sum = 0;
  320.  
  321.     for ( i = 0; i < clrs; ++i )
  322.         {
  323.         r += MPPM_GETR( chv[indx + i].color ) * chv[indx + i].value;
  324.         g += MPPM_GETG( chv[indx + i].color ) * chv[indx + i].value;
  325.         b += MPPM_GETB( chv[indx + i].color ) * chv[indx + i].value;
  326.         sum += chv[indx + i].value;
  327.         }
  328.     r = r / sum;
  329.     if ( r > MAXVAL ) r = MAXVAL;    /* avoid math errors */
  330.     g = g / sum;
  331.     if ( g > MAXVAL ) g = MAXVAL;
  332.     b = b / sum;
  333.     if ( b > MAXVAL ) b = MAXVAL;
  334.     MPPM_ASSIGN( colormap[bi], r, g, b );
  335. #endif /*REP_AVERAGE_PIXELS*/
  336.     }
  337.  
  338.     /*
  339.     ** All done.
  340.     */
  341.     return newcolors;
  342.     }
  343.  
  344. static int
  345. redcompare( ch1, ch2 )
  346.     colorhist_vector ch1, ch2;
  347.     {
  348.     return (int) MPPM_GETR( ch1->color ) - (int) MPPM_GETR( ch2->color );
  349.     }
  350.  
  351. static int
  352. greencompare( ch1, ch2 )
  353.     colorhist_vector ch1, ch2;
  354.     {
  355.     return (int) MPPM_GETG( ch1->color ) - (int) MPPM_GETG( ch2->color );
  356.     }
  357.  
  358. static int
  359. bluecompare( ch1, ch2 )
  360.     colorhist_vector ch1, ch2;
  361.     {
  362.     return (int) MPPM_GETB( ch1->color ) - (int) MPPM_GETB( ch2->color );
  363.     }
  364.  
  365. static int
  366. sumcompare( b1, b2 )
  367.     box_vector b1, b2;
  368.     {
  369.     return b2->sum - b1->sum;
  370.     }
  371.